package top.minuy.structure.graph.bridge;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.HashSet;
import java.util.Set;

/**
 * 寻找图中的割点
 *
 * @author Minuy
 * @time 23:31
 * @date 2021/11/21
 */
public class FindCutVertex {

    Graph g;
    int count;
    int[] ord;
    int[] low;
    boolean[] isVisited;
    Set<Integer> cutVertex;


    public FindCutVertex(Graph g) {
        this.g = g;

        isVisited = new boolean[g.V()];

        low = new int[g.V()];
        ord = new int[g.V()];

        cutVertex = new HashSet<>();

        count = 0;

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent) {
        isVisited[v] = true;
        ord[v] = count;
        low[v] = ord[v];
        count++;

        int child = 0;

        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) {
                dfs(w, v); // 遍历
                low[v] = Math.min(low[w], low[v]); // 然后看它是否联通祖先顶点


                /*
                 * .  0          0           0
                 * .   \          \         / \
                 * .    x          x       n   x
                 * .     \        / \       \  /
                 * .      s      s - n       s
                 * .     s>x      s=x       s<x
                 * 如上，x不是root的情况下，>=的情况是割点，<的情况不是
                 */
                if (v != parent && low[w] >= ord[v]) {
                    cutVertex.add(v);
                }

                /*
                 * .   root    root
                 * .   / \     / \
                 * .  s   n   s - n
                 * 如上，是根顶点时，有没有被访问的两个孩子，说明是割点（1）
                 * （2）的root不是割点，但是也有两个孩子啊？
                 * 深度优先遍历时，n在被从root访问前，已经被s访问，
                 * 所以child计数需要在未访问中计数，然后再判断child
                 */
                child++;
                if (v == parent && child > 1)
                    cutVertex.add(v);

            } else if (w != parent) {
                /*
                 * .     0
                 * .   /   \
                 * . 1      2
                 * .  \    /
                 * .    3
                 * 对于从0开始，到2的情况，
                 * 0不是2的父顶点，
                 * 并且被访问过了
                 */
                low[v] = Math.min(low[w], low[v]);
            }
        }
    }

    public Iterable<Integer> cutVertex(){
        return cutVertex;
    }

}
